# To change this template, choose Tools | Templates
# and open the template in the editor.

from UndirectedGraph import  UndirectedGraph
from Queue import Queue

def BFS(graph,startNode):
#Implementation of Breadth First Search
#Input:
#graph - the graph to be traversed
#startNode - the initial Node
#Output:
#parent - dictionary of (node,parent) mappings
#distNode - dictionary of (node,distance of node from startNode) mappings
    foundNotHandled = Queue()
    foundNotHandled.enqueue(startNode)
    foundHandled = []
    # Mappings initialized
    parent = {}
    distNode = {}
    parent[startNode]='None'
    distNode[startNode]=0
    #loop
    while(True):
        if (foundNotHandled.__len__()==0):
            break
        node = foundNotHandled.dequeue()
        for neighbour in graph.getAdjacentEdges(node):
            if (foundNotHandled.__contains__(neighbour)==False and foundHandled.__contains__(neighbour)==False):
                foundNotHandled.enqueue(neighbour)
                parent[neighbour]=node
                distNode[neighbour]=distNode[node]+1
        foundHandled.append(node)
    return (parent,distNode)

__author__="abhi"
__date__ ="$27 Mar, 2010 10:40:26 PM$"

if __name__ == "__main__":
    print "Hello World";

    g = UndirectedGraph();

    g.addEdge('a', 'b')
    g.addEdge('b', 'c')
    g.addEdge('a', 'b')
    g.addEdge('x', 'y')
    g.addEdge('y', 'z')
    g.addEdge('z', 'y')
    g.addEdge('x', 'z')
    g.addEdge('b', 'x')

    parent,distMap = BFS(g, 'a')

    print(parent)
    print(distMap)